<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2971：魔法森林</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">魔法森林</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">魔法森林</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                魔法森林                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div><span style="font-size: medium">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 你一定听说过魔法森林吧。难道没有吗？至少从精灵的传说里听说过它吧？虽然没有人知道它到底在那里，但许许多多的传说证明了它的存在。比如有人说，没有人进了魔法森林，还能找到回来的路。无论如何，人们知道魔法森林是一个矩形，如果我们把它分成单位正方形，在每个正方形里正好有一棵树。如果你有时间去听村里最年长的老者讲故事，他们甚至会告诉你关于魔法森林的更奇异的事情。</span></div>
<div><span style="font-size: medium">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 这个魔法森林是怎样来的呢？魔法森林最初只是普通的森林，在它周围很远的地方都没有其他森林。但是有一天&hellip;&hellip;这是春天里的一个阳光灿烂的日子，森林里的所有居民都很高兴。但突然一声熊猫的吼叫宣告了伟大的森林议会就要开始了。所有动物放下它们的工作，立即赶往议会。其中刺猬Harry来得最慢，于是鸟们开始没有耐性地唱歌，苍蝇们开始飞来飞去（不断地），野鹿开始发出一些奇怪地声音，老狐狸正在狡猾地观察着她身边的所有东西，而那只大黑熊又开始感到饥饿了，于是它开始用草莓充饥。没有人知道将会发生什么，没有人&mdash;&mdash;除了Olivia&mdash;&mdash;一只聪明的猫头鹰。</span></div>
<div><span style="font-size: medium">&nbsp;</span></div>
<div><span style="font-size: medium"><i>&mdash;我亲爱的朋友们，我相信每个人都同意这点&mdash;&mdash;我们的森林不能让一个游客的眼睛感到非常愉快。森林里有太多种树了。更确切地说，有两种&mdash;&mdash;松树和柏树。我们应该把其中一种树全部消灭掉。你们建议消灭哪种呢？</i></span></div>
<div><span style="font-size: medium"><i>－&ldquo;谁在乎呢&hellip;&hellip;&rdquo;大黑熊喃喃自语地说道，然后它又一口把另一个草莓吃了下去。大多数其他的动物都感到非常困惑，它们都没有听明白。</i></span></div>
<div><span style="font-size: medium"><i>－好了，接下来我要问第二个问题了：我们应该怎样干掉那些树呢？</i><i>Olivia</i><i>说道。</i></span></div>
<div><span style="font-size: medium">&nbsp;</span></div>
<div><span style="font-size: medium">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 就在这个时候，一个巫师在一束亮光之下出现了。（在这之前他一直藏在一棵树后面。）他的名字是Genzibabel。事实上，这些消灭树的计划都是他的主意&mdash;&mdash;他想练习一下他刚学会的魔法。于是他开始对动物们说：</span></div>
<div><span style="font-size: medium">&nbsp;</span></div>
<div><span style="font-size: medium"><i>－我可以把你们的森林里的树全部变成其中一种。我可以施展一种叫做</i><i>Floodfill-Altertree</i><i>的魔法。我需要做的只是选定其中一棵树，然后我会施展魔法。在魔法放出的一瞬间，我选中树所在的一片和它相同种类的树都会变成另外一种树（也就是说，松树变成柏树，柏树变成松树）。用这个方法，我可以用一次魔法就把一整片相同树的连接区域变成另外一种。但是施展这个魔法是非常辛苦的（要耗费</i><i>MP</i><i>啊！）</i><i>,</i><i>所以我想尽可能少地使用这个魔法。</i></span></div>
<div><span style="font-size: medium">&nbsp;</span></div>
<div style="text-indent: 21pt"><span style="font-size: medium">要记住，我们可以把森林想象成由树组成的矩形。两棵树相邻当且仅当他们所在的单位正方形有公共边。你要解决的问题正和这个巫师还有这些动物们一样。你要求出最少要施展多少次魔法才可以把所有的树只变成一种。</span></div></p><hr/><h3>输入格式</h3><p><div style="text-indent: 21pt"><span style="font-size: medium">输入文件的第一行有一个数B，表示下面有B组数据。每组数据第一行有两个整数R,C（1&lt;=R,C&lt;=150），表示森林的行数和列数。再下面是一个R行C列的01矩阵，表示森林。1表示松树，0表示柏树。矩阵的任何位置没有空格。</span></div></p><hr/><h3>输出格式</h3><p><div><span style="font-size: medium">&nbsp;&nbsp;&nbsp;&nbsp; 每组数据输出一行，每行一个整数：最少施展魔法的次数。</span></div></p><hr/><h3>样例输入</h3><pre>2
1 10
1011001101
9 9
001111100
010000010
100101001
100101001
100000001
101000101
100111001
010000010
001111100
</pre><hr/><h3>样例输出</h3><pre>3
2
【样例解释】
第一组数据依次在(1,2),(1,9),(1,5)施法，第二组依次在(2,3),(3,1)施法。
【数据约定】
1≤R,C≤150。
对于40%的数据有R*C≤35*35。</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2971" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2971" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>